using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Geometry;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PublicClass
{
    /// <summary>
    /// 四叉树的节点实体数据
    /// </summary>
    public class NodeEntData
    {
        public Extents3d Extents3d { get; set; }
        public Entity Entity { get; set; }

        /// <summary>
        /// 扩展数据
        /// </summary>
        public object ExData { get; set; }
        public NodeEntData()
        {
            Extents3d = new Extents3d();
            Entity = null;
            ExData = null;
        }
        public NodeEntData(Entity ent)
        {
            Extents3d = new Extents3d();
            Entity = ent;
            if (null != ent)
                Extents3d = ent.GeometricExtents;
            ExData = null;
        }
    }

    // 四叉树节点
    public class QuadTreeNode
    {
        private Extents3d extent = new Extents3d();
        /// <summary>
        /// 外包
        /// </summary>
        public Extents3d Extents3d
        {
            get
            {
                return extent;
            }
            set
            {
                extent = value;
            }
        }

        /// <summary>
        /// 在这个区域范围内，横跨子区域的实体
        /// </summary>
        public List<NodeEntData> AllEntLst { get; set; }

        /// <summary>
        /// 扩展数据
        /// </summary>
        public object ExData { get; set; }

        /// <summary>
        /// 子节点，按需创建,只有四个(左上，左下，右上，右下)
        /// </summary>
        public List<QuadTreeNode> AllChildNode { get; set; }

        public int NodeDeep { get; set; }

        public QuadTreeNode()
        {
            ExData = null;
            Extents3d = new Extents3d();
            AllEntLst = new List<NodeEntData>();
            AllChildNode = new List<QuadTreeNode>();
            NodeDeep = 0;
        }
        public void DevFoure(int nCount = 2)
        {
            if (nCount < 1)
                nCount = 2;

            if (AllChildNode.Count > 0)
                AllChildNode.Clear();

            double dWidth = Extents3d.Width();
            double dHeight = Extents3d.Height();

            double dOneWidth = dWidth / nCount;
            double dOneHeight = dHeight / nCount;

            int nChild = nCount * nCount;
            Point3d ptLeftBootom = Extents3d.MinPoint;
            for (int i = 0; i < nCount; i++) // 行
            {
                Point3d ptBootom = ptLeftBootom;
                for (int j = 0; j < nCount; j++) // 列
                {
                    QuadTreeNode nodeChild = new QuadTreeNode();
                    Point3d ptRightTop = ptBootom + Vector3d.XAxis * dOneWidth;
                    ptRightTop = ptRightTop + Vector3d.YAxis * dOneHeight;
                    nodeChild.Extents3d =
                        new Extents3d(ptBootom, ptRightTop);
                    ptBootom += Vector3d.XAxis * dOneWidth;
                    // debug
                    // CadCurve.DrawExtent(nodeChild.Extents3d);
                    nodeChild.NodeDeep = NodeDeep + 1;
                    AllChildNode.Add(nodeChild);
                }
                ptLeftBootom += Vector3d.YAxis * dOneHeight;
            }
        }
    }

    // 四叉树
    public class QuadThree
    {
        public double m_dLength = 32000;//默认范围32km
        public double m_dWidth = 32000;//默认范围32km
        public int m_nMaxDeep = 8;//最大深度4的8次方个网格

        QuadTreeNode m_root = null;
        public QuadThree(Extents3d exAll)
        {
            Init(exAll, true);
        }

        private void QuadTreeBuild(Extents3d exAll)
        {
            m_root = new QuadTreeNode();
            m_root.Extents3d = exAll;

        }
        private bool Init(Extents3d exAll, bool bAll = false)
        {
            if (null == exAll)
                return false;
            if (bAll)
            {
                m_dWidth = exAll.Width();
                m_dLength = exAll.Height();
                double dWidth = Math.Max(m_dWidth, m_dLength);
                m_dWidth = dWidth;
                m_dLength = dWidth;
            }

            Point3d ptCenter = exAll.GetCenterPoint();
            m_root = new QuadTreeNode();
            Point3d ptMin = new Point3d(ptCenter.X - m_dLength / 2, ptCenter.Y - m_dWidth / 2, 0);
            Point3d ptMax = new Point3d(ptCenter.X + m_dLength / 2, ptCenter.Y + m_dWidth / 2, 0);
            m_root.Extents3d = new Extents3d(ptMin, ptMax);

            DevFoure(m_root);


            return true;
        }

        void DevFoure(QuadTreeNode node)
        {
            if (node.NodeDeep + 1 == m_nMaxDeep)
                return;

            node.DevFoure();

            foreach (var item in node.AllChildNode)
            {
                DevFoure(item);
            }
        }

        /// <summary>
        /// 加入实体
        /// </summary>
        /// <param name="en"></param>
        public void AddEntity(NodeEntData node)
        {
            if (node == null)
                return;
            if (m_root == null)
            {
                return;
            }

            AddEntityToNode(m_root, node);
        }

        /// <summary>
        /// 找到点所在处实体
        /// </summary>
        /// <param name="pt"></param>
        /// <returns></returns>
        public List<NodeEntData> GetEntityAtPoint(Point3d pt)
        {
            List<NodeEntData> lstRet = new List<NodeEntData>();
            Find(m_root, pt, ref lstRet);
            return lstRet;
        }

        public List<NodeEntData> RectSearch(Point3d pt1, Point3d pt2)
        {
            List<NodeEntData> lstRet = new List<NodeEntData>();
            Extents3d ex = new Extents3d();
            ex.AddPoint(pt1);
            ex.AddPoint(pt2);
            RectSearch(m_root, ex, ref lstRet);
            return lstRet;
        }
        static bool AddNodeToList(List<NodeEntData> lstRet, NodeEntData node)
        {
            if (null == node)
                return false;

            if (lstRet.Contains(node))
                return false;

            lstRet.Add(node);
            return true;
        }
        void RectSearch(QuadTreeNode node, Extents3d ex, ref List<NodeEntData> lstRet)
        {
            for (int i = 0; i < node.AllEntLst.Count; ++i)
            {
                if (node.AllEntLst[i].Extents3d.ExtsIsIntersect(ex))
                {
                    AddNodeToList(lstRet, node.AllEntLst[i]);
                }
            }
            if (!node.Extents3d.ExtsIsIntersect(ex))
                return;

            //子节点 
            foreach (QuadTreeNode child in node.AllChildNode)
            {
                if (child.Extents3d.ExtsIsIntersect(ex))
                {
                    RectSearch(child, ex, ref lstRet);
                }
            }
        }

        /// <summary>
        /// 加入实体到节点
        /// </summary>
        /// <param name="node"></param>
        /// <param name="entNode"></param>
        /// <param name="nDeep"></param>
        bool AddEntityToNode(QuadTreeNode node, NodeEntData entNode)
        {
            // 包含
            if (!node.Extents3d.ContainsXY(entNode.Extents3d))
            {
                return false;
            }

            if (node.AllChildNode.Count == 0)
                node.AllEntLst.Add(entNode);
            else
            {
                foreach (var item in node.AllChildNode)
                {
                    if (AddEntityToNode(item, entNode))
                        return true;
                }
            }

            //不能被任何一个子节点完全覆盖，就放到当前节点 
            node.AllEntLst.Add(entNode);


            return true;
        }

        /// <summary>
        /// 找到点所在处实体
        /// </summary>
        /// <param name="node"></param>
        /// <param name="pt"></param>
        /// <param name="lstRet"></param>
        void Find(QuadTreeNode node, Point3d pt, ref List<NodeEntData> lstRet)
        {
            if (node == null)
                return;

            for (int i = 0; i < node.AllEntLst.Count; ++i)
            {
                if (node.AllEntLst[i].Extents3d.ContainsXY(pt))
                {
                    lstRet.Add(node.AllEntLst[i]);
                }
            }
            //子节点 
            foreach (QuadTreeNode child in node.AllChildNode)
            {
                if (child.Extents3d.ContainsXY(pt))
                {
                    Find(child, pt, ref lstRet);
                }
            }
        }
    }
}
